package LeetCode;

/**
 * @Classname LC300
 * @Description // https://leetcode-cn.com/problems/longest-increasing-subsequence/  最长递增子序列
 * @Date 2021/4/20 23:38
 * @Created by yin
 */
public class LC300 {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];// dp[i]表示以index = i 结尾的子数组的最长子序列长度
        for (int i = 0; i < len; i++) dp[i] = 1; // 注意：初始化的时候都为1
        // 长度从 0 到 len
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {  // nums[j]遍历前面的，如果存在比nums[j]小的，则更新
                if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        int ans = 0;
        for (int num : dp) {
            ans = Math.max(num, ans);
        }
        return ans;
    }

    // 二分查找法  详情参考 ./imgs/LC300.png
    public int lengthOfLIS2(int[] nums) {
        int piles = 0;
        int[] ans = new int[nums.length];
//         搜索左侧边界的二分查找
        for (int num : nums) {
            // num 记录了牌顶的元素
            int left = 0, right = piles;
            while (left < right) {
                int mid = (left + right) / 2;
                if (ans[mid] > num) right = mid;
                if (ans[mid] < num) left = mid + 1;
                else right = mid;
            }
            // 如果没有找到合适的牌堆
            if (left == piles) piles++;
            ans[left] = num;
        }
        return piles;

    }
}
